# -*- coding: utf-8 -*-
"""https://leetcode.com/problems/number-of-digit-one/

Given an integer n, count the total number of digit 1
appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
"""


class Solution:
    # @param {integer} n
    # @return {integer}
    def countDigitOne(self, n):
        if n < 10:
            return 1
        if n <= 100:
            return self.calc_down100(n, 0)

        index = 0
        while n > 10**index:
            index += 1

        index -= 1
        hdigit = n / (10 ** index)

        if hdigit == 1:
            count = 1
        else:
            count = (hdigit - 1) * index * (10 ** (index - 1))


        n = n - (10 ** index) * hdigit
        while n > 0:
            subhdigit = n / (10 ** index)

            if subhdigit == 1:
                count += index * (10 ** (index - 1))
            else:
                count += (hdigit - 1) * index * (10 ** (index - 1))

            index -= 1
            n = n - (10 ** index) * hdigit

            if n < 100:
                count = self.calc_down100(n, count)

                n = 0
        print '---->', index, count
        return count

    def calc_down100(self, n, count):
        ssubhdigit = n / 10
        if ssubhdigit > 1:
            count += 10
            count += (ssubhdigit - 2)
            if n > (ssubhdigit * 10 + 1):
                count += 1
        elif ssubhdigit == 1:
            count += (n - 10) + 1 + 1
        return count


n = Solution().countDigitOne(101)
print n